#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-15 10:00 上午
# @Author  : yangdy
# @File    : 2020-07-15.96. 不同的二叉搜索树
# @Software: PyCharmCE


class Solution:
    def numTrees(self, n: int) -> int:
        ans = 0
        # 1.dp
        # dp = [0 for i in range(n+1)]
        # dp[0] = 1
        # for i in range(1, n+1):
        #     for j in range(0, i):
        #         dp[i] += dp[j] * dp[i-1-j]
        # ans = dp[n]
        # 2.catalan

        def comb(mm, nn):
            if mm <= nn:
                return 1
            ret = 1
            for i in range(mm, nn, -1):
                ret *= i
            for i in range(1, mm-nn+1):
                ret //= i
            return ret

        ans = comb(2*n, n) - comb(2*n, n-1)
        return ans


solve = Solution()

questions = [
    (3,),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print('ans:', solve.numTrees(q[0]))
